class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k)
    {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int min = INT_MAX, ret = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            if (nums[i] < 0 && k>0) nums[i] *= -1, k--;
            min = std::min(min, nums[i]);
            ret += nums[i];
        }
        if (k % 2 == 1)
        {
            ret -= 2 * min;
        }

        return ret;
    }
};